//class TreeNode {
//    int val;
//    TreeNode left;
//    TreeNode right;
//    TreeNode(int x) { val = x; }
//}


/**
 * 力扣：236 二叉树的最近公共祖先
 */

//1.二叉搜索树
class Solution7 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        if(root == p || root == q) {
            return root;
        }
        TreeNode retLeft = lowestCommonAncestor(root.left,p,q);
        TreeNode retRight = lowestCommonAncestor(root.right,p,q);
        //如果在左子树和右子树都能找到节点，那么根节点就为公共祖先
        if(retLeft != null && retRight != null) {
            return root;
        }else if(retLeft != null) {
            //如果左子树不为空，则返回左子树最先碰到的节点
            return retLeft;
        }else{
            //如果右子树不为空，则返回右子树最先碰到的节点
            return retRight;
        }

    }
}